package com.yu1996.linkedlist;


/**
 * @Description: 约瑟夫问题
 * @author: xing
 * @Date: 2019/8/3 12:43
 */
public class Josepfu {

    public static void main(String[] args) {

        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.addBoy(25);
        list.showBoys();
//        System.out.println("当前链表长度为：" + list.getLength());
        System.out.println("约瑟夫：");
        list.showByNum(1, 2);

    }
}


/**
 * @Description: 单向循环链表
 * @author: xing
 * @Date: 2019/8/3 13:07
 */
class CircleSingleLinkedList {

    //定义一个指针指向第一个节点孩子
    private Boy first = null;


    public int getLength() {
        Boy temp = first;
        int length = 1;
        while (temp.getNext() != first) {
            length++;
            temp = temp.getNext();
        }
        return length;
    }

    /**
     * @Description 添加nums个孩子节点进入链表
     * @Author xing
     * @Date 2019/8/3 13:07
     * @Return
     * @Exception
     */
    public void addBoy(int nums) {
        //对nums进行数据校验
        if (nums < 1) {
            System.out.println("输入nums不合法");
            return;
        }

        //定义辅助节点用于指向当前链表的最后节点孩子
        Boy cueBoy = null;
        for (int i = 1; i <= nums; i++) {
            //创建新的孩子节点
            Boy boy = new Boy(i);
            //判断是否为第一个孩子节点
            if (i == 1) {
                first = boy;
                boy.setNext(first);
                cueBoy = boy;
            } else {
                cueBoy.setNext(boy);
                boy.setNext(first);
                cueBoy = boy;
            }
        }
    }


    /**
     * @Description 遍历当前单向循环链表
     * @Author xing
     * @Date 2019/8/3 13:08
     * @Return
     * @Exception
     */
    public void showBoys() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("当前链表为空");
            return;
        }
        //定义遍历指针
        Boy curBoy = first;
        while (true) {
            System.out.printf("第%d个小孩是：%d\n", curBoy.getNo(), curBoy.getNo());
            if (curBoy.getNext() == first) {
                break;
            }
            curBoy = curBoy.getNext();
        }
    }


    /**
     * @Description 约瑟夫问题解决   num：第几个开始   k：一次数几下
     * @Author xing
     * @Date 2019/8/4 10:20
     * @Return
     * @Exception
     */
    public void showByNum(int num, int k) {

        //对num进行校验
        if (num < 1 || num > getLength() || k < 1) {
            System.out.println("输入数字不合法");
            return;
        }
        //定义辅助节点指向被删除节点的前一个节点
        Boy curBoy = first;
        //用while循环遍历链表将curBoy指向最后一个节点
        while (true) {
            if (curBoy.getNext() == first) {
                break;
            }
            curBoy = curBoy.getNext();
        }
        //做准备：让curBoy和first移动到开始的位置
        for (int i = 0; i < num - 1; i++) {
            first = first.getNext();
            curBoy = curBoy.getNext();
        }

        //开始
        while (true) {
            //判断出循环条件  当只有最后一个节点是跳出循环
            if (first.getNext() == first) {
                System.out.printf("最后一个小孩的是：%d\n", first.getNo());
                break;
            }
            //开始移动位置
            for (int y = 0; y < k - 1; y++) {
                first = first.getNext();
                curBoy = curBoy.getNext();
            }
            System.out.printf("当前小孩%d出圈\n", first.getNo());
            first = first.getNext();
            curBoy.setNext(first);
//            //再将curBoy和first移动到指点的位置
//            for (int i = 0; i < num - 1; i++) {
//                first = first.getNext();
//                curBoy = curBoy.getNext();
//            }
        }

    }

}


/**
 * @Description: 单向循环链表的节点
 * @author: xing
 * @Date: 2019/8/3 13:08
 */
class Boy {
    private Integer no;
    private Boy next;

    public Boy(Integer no) {
        this.no = no;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}